﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

public class Solution148
{
    //冒泡,超时
    public ListNode SortList2(ListNode head)
    {

        if(head == null || head.next == null)
        {
            return head;
        }
        ListNode dummyHead = new ListNode(-1,head);

        //使用flag

        bool flag=true;



       
        while (flag)
        {

            flag = false;
            ListNode pre = dummyHead;
            ListNode cur = dummyHead.next;
            ListNode next = cur.next;

            while (next != null)
        {
               
                Console.WriteLine("cur.val:  "+cur.val+ "  next.val:  " + next.val );
            if (cur.val > next.val)
            {
                    //交换
                    flag = true;

                    cur.next = next.next;
                next.next = cur;
                pre.next = next;
                
                //更新下一个节点
                pre = next;
                next = cur.next;


            }
            else
            {
                pre= cur; 
                cur = next;
                next = next.next;
            }



        }

        }

        return dummyHead.next;



    }
    //归并
    public ListNode SortList(ListNode head)
    {

        if( head == null || head.next == null)
        {
            return head;
        }

        ListNode left = head;
        ListNode pre = left;//left前面的节点，应该指向空
        ListNode right = head;
        while (right != null && right.next != null)
        {
            pre = left;
            left = left.next; 
            right = right.next.next;

        }
        pre.next = null;
        ListNode l= SortList(head);
        ListNode r = SortList(left);

       return Merge(l, r);

    }

    private ListNode Merge(ListNode l, ListNode r)
    {
        ListNode head = new ListNode();
        ListNode dummyHead = head;
       

        ListNode lCur = l;
        ListNode rCur = r;
       


        while(lCur != null && rCur != null)
        {
            if (lCur.val < rCur.val)
            {
                ListNode next = lCur.next;

                lCur.next = dummyHead.next;
                dummyHead.next = lCur;
                
                lCur = next;
            }
            else
            {
                ListNode next = rCur.next;

                rCur.next = dummyHead.next;
                dummyHead.next = rCur;
                rCur = next;
            }
            dummyHead = dummyHead.next;

        }

        if(lCur == null)
        {
            dummyHead.next = rCur;
        }
        else
        {
            dummyHead.next = lCur;
        }
        return head.next;


    }
}

class Program148
{


    static void Main148(string[] args)
    {


        ListNode head
            = new ListNode();

        for(int i = 0; i < 5; i++) {
        
        
            ListNode newNode = new ListNode(i);

            newNode.next = head.next; ;
            head.next = newNode;


        }

        Solution148 sol = new Solution148();
        ListNode res= sol.SortList(head);
        while(res != null)
        {
            Console.Write(res.val+",");
            res=res.next;
        }


    }
}
